Linux pi_futex浅析

注

Priority Inheritance，优先级继承，是解决优先级反转的一种办法。

一个经典的例子：A/B/C 三个实时进程，优先级 A>B>C。C 持有 a 锁，而 A 等待 a 锁被挂起。原本 C 释放 a 锁之后，A 进程就可以继续执行的，但是偏偏有个比 C 优先级高的 B 进程存在，导致 C 得不到运行，也就没法释放 a 锁，从而导致 A 进程一直挂起。从整体上看，进程 B 虽然比 A 优先级低，但它却成功的抢占掉了 A。这就是所谓的优先级反转。

一种解决办法是优先级继承，C 在持有 a 锁期间临时继承等待者 A 的优先级，那么 B 进程就无法从中捣乱了。

为了支持优先级继承，内核里面实现了一个叫 rt_mutex 的互斥锁。内核中的各个部分，包括本文要讨论的 pi_futex，都可以使用 rt_mutex 来实现优先级继承。所以，要分析 pi_futex，先得把 rt_mutex 弄清楚。

rt_mutex 之所以叫 rt_ ，是因为优先级继承主要是为实时进程服务的。我们知道，与普通进程 "根据优先级瓜分 CPU 时间片" 的理念不同，内核总是尽量满足最高优先级的实时进程的 CPU 需求，直到它挂起或退出。对于实时进程来说，优先级反转的后果尤为严重。比如上述例子，考虑在单核机器下，B 进程 "抢占" 掉 A 进程之后，只要 B 进程一直处于 RUNNING 状态，C 进程就得不到执行，A 进程就得一直挂起。而如果是普通进程的话，B 进程很快会用完时间片，就算 "抢占" 了 A 进程，那也只是一瞬间的事情。

要实现优先级继承，内核需要维护一条 PI chain，保存进程持有锁和等待锁的依赖关系。PI chain 其实是一个树型结构：一个 task 可能持有 N 个 rt_mutex、每个 rt_mutex 只能被一个 task 持有。反过来，一个 rt_mutex 可能让 M 个 task 挂起、而每个 task 又只会挂起在一个 rt_mutex 上面。如：

rt_mutex_waiter 结构是作为 task 在 rt_mutex 上挂起时的连接件而存在的，其实它逻辑上应该是 task_struct 的一部分，只不过这个部分只是在 PI chain 中才有用。rt_mutex_waiter.task 和 task_struct.pi_blocked_on 相互指向。

task 通过 pi_waiters 可以遍历到在它持有的每个 rt_mutex 上挂起的最高优先级的 task（称作 top waiter）。这个遍历逻辑都是由 plist（有序链表）提供的，里面挂着的 rt_mutex_waiter 会以其所对应的 task 的优先级来排序。这样，一个 task 能继承到的优先级就是通过 pi_waiters 取到的第一个 rt_mutex_waiter 所对应的 task（称作 top pi waiter）的优先级。因为这里只需要关心最高优先级，所以每个 rt_mutex 只需要将自己的 top waiter 的提供上来就可以了，不必全部加进来。这个遍历关系是 PI chain 中最重要的一环，通过它来完成优先级继承。

rt_mutex 则可以通过 wait_list 来遍历在它身上挂起的 rt_mutex_waiter，从而遍历到挂起的 task。这个遍历关系则是描述锁依赖关系的原始信息，为构建上一种遍历关系而存在。试想，当一个进程新持有一把锁时，rt_mutex.wait_list 中的 top waiter（rt_mutex_waiter）将加入到 task_struct.pi_waiters 链表中；当 rt_mutex.wait_list 中的进程优先级发生变化，导致 top waiter 改变时，需要将原来的 top waiter 从 task_struct.pi_waiters 里面移出，然后把新的 top waiter 加进去。为了这个过程的顺利进行，rt_mutex.wait_list 也是一个按优先级排序的 plist。

上述过程会导致 task 的 pi_waiters 发生变化，可能导致 top pi waiter 改变，从而重置进程优先级。

作为其中核心的 rt_mutex，其实是一个很简单的结构，只有图中所列的 owner 和 wait_list、外加一把 spinlock。对它的上锁操作很简单，把 owner 指针指向持有者进程即可。而 spinlock 则用于保护 lock/unlock 过程，以及将进程挂入 / 移出 PI chain 的过程。

而如果不存在竞争，rt_mutex 可以利用 cmpxchg 原子指令直接尝试 lock/unlock：cmpxchg (rt_mutex.owner, NULL, current) /cmpxchg (rt_mutex.owner, current, NULL)。如果 owner 指针为 NULL，原子性的修改为当前进程，则 lock 成功。否则说明已经被上锁，就需要上 spinlock、然后修改 PI chain；反过来，如果 owner 指针指向当前进程，原子性的修改为 NULL，则 unlock 成功。否则说明锁有等待者（owner 指针会打上 flag，使得它不等于当前进程），需要上 spinlock、修改 PI chain、然后唤醒 top waiter。

有了 rt_mutex 做支撑，pi_futex 就可以登场了。三个耳熟能详的接口：

int futex_lock_pi (int *uaddr);
int futex_trylock_pi (int *uaddr);
int futex_unlock_pi (int *uaddr);

回想一下，futex 的核心思想是什么（参阅《linux futex 浅析》）？那就是用户态的锁变量与内核态 futex 机制的互动。pi_futex 也不例外。

在锁没有竞争的情况下，用户态通过对锁变量的原子指令操作，依然可以完成 pi_futex 的上锁和解锁。但是锁变量的取值跟普通的 mutex 不太一样（普通 mutex 一般用 0 值表示未上锁、1 是上锁、2 是上锁且有进程挂起等待），pi_futex 下，锁变量 0 值表示未上锁，上锁时写入 owner 进程的 tid（全局的线程 id），有进程挂起时在 tid 的基础上增加一个 RT_MUTEX_HAS_WAITERS 标记。

为什么要这样定呢？考虑这么一个场景，锁 a 处于未上锁状态 (*uaddr==0)，然后进程 A 和 B 相继对其做 lock 操作。进程 A 在用户态就能 lock 成功了，而进程 B 则需要调用 futex_lock_pi 进入内核，然后被挂起。进程 B 挂起的时候，A 和 B 应该会形成 PI chain，但是 A 上锁的时候根本就没经过内核。换句话说，内核怎样得知进程 A 的信息，并构造出这条 PI chain 呢？就是通过记在 *uaddr 里面的 tid。当然，这个 tid 是用户自己填的。如果用户乱填，是可以让自己的程序没法工作的：)（可能会让一个不相干的进程莫名其妙的成了 rt_mutex 的 owner，或者 futex_lock_pi 找不到对应 tid 的进程，而返回失败。用户总是可以让自己的程序出问题的，不是么？）

有了 A 进程的 tid，要构造 PI chain 还缺些什么呢？对啊，rt_mutex 都还没创建出来。这就引出了 pi_futex 中的一个最重要的逻辑：uaddr 跟 rt_mutex 的对应。

跟普通 futex 一样，uaddr 在内核中会对应一个 "等待队列"（其实是一个全局的队列）。挂起的进程在等待队列中对应一个 futex_q 结构：

struct futex_q {
    struct plist_node list;             // 链入等待队列
    struct task_struct *task;           // 挂起的进程本身
    spinlock_t *lock_ptr;               // 保存等待队列的锁，便于操作
    union futex_key key;                // 唯一标识 uaddr 的 key 值
    struct futex_pi_state *pi_state;    // 进程正在等待的锁
    struct rt_mutex_waiter *rt_waiter;  // 进程对应的 rt_waiter
    union futex_key *requeue_pi_key;    // 等待被 requeue 的 key
    u32 bitset;                         //futex_XXX_bitset 时使用
};

其中的 pi_state 其实就是 rt_mutex。由于存在于 pi_futex 体系中需要额外的关联信息，所以使用 pi_state 对 rt_mutex 做了包装：

struct futex_pi_state {
    struct list_head list;      // 链入持有者进程的 list
    struct rt_mutex pi_mutex;   // 锁本身
    struct task_struct *owner;  // 锁的持有者进程
    atomic_t refcount;          // 引用计数
    union futex_key key;        // 唯一标识 uaddr 的 key 值
};

futex_pi_state 中的 key 和 pi_mutex 就把 uaddr 跟 rt_mutex 的绑定了起来。

引入这两个结构之后，数据模型变成了这样：

这样一来，持有 uaddr 对应的锁的进程，就持有了内核中对应的 rt_mutex，从而能够获得相应的优先级继承；而在 uaddr 对应的锁上挂起的进程，也就挂起到了相应的 rt_mutex 上，从而优先级被继承。

task 通过 pi_state_list 可以遍历到它所持有的所有 rt_mutex（via pi_state），在进程地址空间销毁（比如 exit、exec）时需要释放这些 rt_mutex（这个链表是关联在 pi_state 上的，如果不是使用 pi_futex，而是内核中直接使用 rt_mutex 呢？就不存在这个自动销毁的逻辑了。不过 rt_mutex 只能内核代码才能直接使用，使用时注意管理好进程的生命周期就好了）。而既然是为销毁而准备的，这个链表只需要普通的 list 就足够了，不需要使用有序的 plist。

这里面最难理解的地方还在于 pi_state.owner 和 rt_mutex.owner。它们不是同一个东西么？为什么会有两个 owner 指针？难道一个锁能被多个进程持有？这个东西的存在主要是为了解决 pi_futex 执行过程中的一些中间状态，可能 pi_state.owner 指向某一进程，而 rt_mutex.owner 为空（未上锁）。此时，被 pi_state.owner 指向的进程被称作是 pending owner。来看看具体的场景：

对于 futex_unlock_pi 来说，它不能像普通的 unlock 操作那样，将 * uaddr 置为 0，然后唤醒一个等待进程就完事。当 rt_mutex 还有进程在挂起等待的时候，绝不能将 * uaddr 设为 0，因为这将使得新的 owner 直接在用户态就 lock 成功，没法建立起与 waiter 们的继承关系（如果没有 waiter，在用户态完成 lock 就无所谓，但是现在情况不一样）。

实现上，unlock 会保持 * uaddr 的上锁状态，但是会将对应的 rt_mutex unlock 掉（否则被唤醒的进程不可能 lock 成功）。并且，将 * uaddr 改成继任者的 tid+flags，pi_state.owner 也已经指向继任者，这时的继任者成为 pending owner。

另一方面，被唤醒的进程在离开 futex_lock_pi 之前（注意，它是在 futex_lock_pi 里面进入睡眠的，醒来的时候还在 futex_lock_pi 里面），futex_lock_pi 需要为它获取到锁，让它真正成为锁的 owner（获取到已经 unlock 的 rt_mutex，并修改 PI chain）。

当然，唤醒之后 futex_lock_pi 获取 rt_mutex 不一定能成功，可能有新来的进程参与竞争，或者之前等待队列中的进程被信号唤醒了，也来重新参与竞争。不过没关系，这将导致被唤醒的进程继续被挂起，并不会从 futex_lock_pi 返回。（如果 pending owner 醒来后锁被别的进程抢走了，称作 lock stealing。）

且说这时可能会有多个进程同时竞争一个 rt_mutex，既然 PI chain 已经保存了进程的优先级关系，竞争的结果也应该是让优先级最高的进程获得锁。futex_unlock_pi 会选择唤醒 rt_mutex 下的 top waiter 进程，并将其置为 pending owner。如果多个 waiter 进程优先级相同，则遵循先来后到的原则，先来的被认为是 top waiter。于是，当进程 futex_lock_pi 时，能否获得 rt_mutex，不是看谁下手快，而是看谁有这个资格：如果进程是 futex_unlock_pi 选中的 pending owner，那么应该让它获得锁；如果进程是新来的，并且优先级比 top waiter 进程还高（高于。如果只是等于，则应该去排队），那么也应该让它获得锁（lock stealing）。如果多个进程都有资格，那只好看谁下手快了。然后被唤醒的进程并不会从 PI chain 中移出，因为这个进程被唤醒之后要么得不到锁（lock stealing），会继续等待；要么会获得锁，那么应该届时再调整 PI chain。

为什么要搞这么复杂呢？简单一点：unlock 时直接将锁释放、将被唤醒的进程移出 PI chain；然后被唤醒时的 futex_lock_pi 直接返回，让用户态去重试。这样不行么？乍一看，虽然被唤醒的进程要被从 PI chain 移出移进，有些冗余，但是似乎还是可以工作的，只要每次唤醒的是最高优先级的进程，它重新去 lock 的时候肯定应该是能够获得锁的。不过考虑一下 rt_mutex 的前几个 waiter 拥有相同优先级的情况，被唤醒的进程如果脱离了 PI chain，重新去 lock，那它就成了新来的。按规矩，它应该遵循先来后到原则，排在其他相同优先级的 waiter 之后，而不能获得锁。如此一来，就没有人能获得锁了。所以 pending owner 这么一个中间状态是有必要的，以区别被唤醒的进程和新来的进程。

那么，futex_lock_pi 如果不在返回之前获得锁行不行呢？返回用户态，等用户态去重新调用 futex_lock_pi，这个看上去貌似也没问题。不过考虑一下 futex_lock_pi 返回用户态后，进程挂掉的情况。被唤醒的 top waiter 竟然挂了，再也不会去尝试持有锁了，队列里的 waiters 又该怎么办呢？（注意，如果 futex_lock_pi 先获得锁，返回用户态后再挂掉，内核会有回收机制，参见前面提到过的 task_struct.pi_state_list。）（再注意，普通 futex 其实并没有这么强的保护。对于普通 futex 来说，内核的功能非常轻，仅仅是给用户态提供一个睡眠唤醒的机制。只要进程退出，futex 等待队列中维护的对应节点自然会被清理。用户再怎么玩都无所谓。而 pi_futex 在内核里面则是非常重，内核需要保证功能的完整性。）

所以内核里面的条原则，不能让 pi_futex 在有 waiter 而没有 owner 的情况下离开内核态，否则可能就没人能成为 owner 了，一堆 waiter 将无人解救。

另外一个问题是关于 futex_trylock_pi。既然是 futex，trylock 操作不是应该由用户态的原子操作来实现么？为什么还要有 trylock 系统调用？的确，pi_futex 系列刚诞生的时候是没有 futex_trylock_pi 的。

用户态的 trylock 只能在未上锁的情况下才能成功，而 futex_trylock_pi 会进入内核，如果 rt_mutex 暂时没有 owner（比如旧的持有者已经 unlock 了，被唤醒的 pending owner 还尚未 lock），且当前进程优先级更高，则可以上锁成功（lock stealing）。

另一方面，进程有时候可能不知道自己有没有持有 pi_futex（比如 futex_lock_pi 被信号打断时，在信号处理函数中拿不到 futex_lock_pi 的返回值，不知道是否上锁成功了）。这时可以调用 futex_trylock_pi 去检查（如果直接调用 futex_lock_pi 可能会死锁）。通过 * uaddr==gettid () 去检查可以么？因为 * uaddr 上会被内核打上其他标记，直接检查很可能通不过，而用户态又不应该去识别这些标记。

除了最普通的 lock/trylock/unlock 三个接口，pi_futex 还有两个接口：

int futex_wait_requeue_pi (int *uaddr1, int val1, int *uaddr2);
int futex_cmp_requeue_pi (int *uaddr1, int n1, int *uaddr2, int n2, int val);

futex_cmp_requeue_pi 是 pi 版本的 futex_cmp_requeue，可以用于带 pi 的 phread_cond_broadcast。有个问题，pi 是针对 mutex 而言的，那么既然是 phread_cond，跟 pi 又有什么关系呢？的确，phread_cond 是没有优先级继承这回事情的，但是 phread_cond 需要跟 mutex 配合使用，而 mutex 则可能是带 pi 的。回想一下，phread_cond_broadcast 为了避免 "惊群"，会使用 futex_cmp_requeue 唤醒一个 waiter，然后将其他 waiter 移动到 mutex 的等待队列上去。那么，如果 mutex 是带 pi 的，简单的将其移动到等待队列显然不够，需要调用 futex_cmp_requeue_pi，完成 PI chain 的构建。

于是，随着 futex_cmp_requeue_pi 被调用，一个 pthread_cond 的 waiter 被唤醒，其他 waiter 被移动到 rt_mutex 的等待队列中，组建 PI chain。然后被唤醒的进程会去调用 futex_lock_pi 尝试加锁…… 稍等，是不是有什么问题？这不是又跟 futex_unlock_pi 时的情形一样了么？不能够放任 rt_mutex 没有 owner，而让被唤醒的进程自己去上锁的呀！

所以，futex_cmp_requeue_pi 不能只是简单的将进程唤醒，还需要将其置为 pending owner。另一方面，pthread_cond_wait 的进程不能只是使用 futex_wait 去等待 pthread_cond，那样的话没法保证返回用户态时已经获得 pi_futex 的锁。而等待 pthread_cond 的场景又跟 futex_lock_pi 不一样，于是 futex_wait_requeue_pi 就诞生了，它需要等待普通 futex（futex_wait 的前半部分），并且在被唤醒后获取 pi_futex（futex_lock_pi 的后半部分）。

futex_cmp_requeue_pi 唤醒进程的做法跟 futex_unlock_pi 不太一样，后者原本是锁的 owner，所以可以由它来指定继任者 pending owner；而前者并不是 owner，它所唤醒的进程不应该成为 pending owner（owner 都没说话呢）。所以 futex_cmp_requeue_pi 会调用 rt_mutex 的 trylock 操作，尝试为被唤醒的进程获得锁。如果成功，那么被唤醒的进程将直接晋升为 owner；否则说明锁的 owner 还在，那就不用唤醒了，直接加入等待队列去。

另一方面，futex_wait_requeue_pi 可能会面对两种情况，它可能被 futex_cmp_requeue_pi 直接唤醒；或者是被放入等待队列，再被随后的 futex_unlock_pi 唤醒。如前所述，第一种情况下被唤醒时进程已经是锁的 owner；而第二种情况则还是 pending owner，还需要为成为 owner 再努一把力。futex_wait_requeue_pi 需要能 handle 这两种情况。

题外话，最近 futex 曝出了提权漏洞，代号 CVE-2014-3153（见：https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-3153）。

问题出在哪里呢？回顾一下之前的数据结构图，当一个进程要在 rt_mutex 上挂起时，加入等待队列，需要一个 futex_q 结构、加入 PI chain，需要一个 rt_mutex_waiter 结构。由于这两个东西都只是在挂起的时候会用到，所以将它们定义在栈上。

在调用 futex_wait_requeue_pi 的时候，情况比较特殊。此时 wait 的是一个普通 futex，而期望被 requeue 的地方是一个 pi_futex。尽管当前 wait 的地方不涉及 PI chain，不需要用到 rt_mutex_waiter，但这个东西可能在被 requeue 的时候用到，所以进程挂起之前得一并定义好：

struct rt_mutex_waiter rt_waiter;
struct futex_q q = futex_q_init;
q.rt_waiter = &rt_waiter;

前面说过，futex_wait_requeue_pi 可能有两个结局，要么成为 rt_mutex 的 owner 被直接唤醒，要么在 rt_mutex 上挂起等待。前一种情况下 rt_waiter 是不需要使用的，后者则不然。

为了区别直接被 futex_cmp_requeue_pi 唤醒，和挂起后再被 futex_unlock_pi 唤醒两种情况，futex_cmp_requeue_pi 直接唤醒时会将 q.rt_waiter 置 NULL，表示 rt_waiter 根本没有使用过，可以不用管了。而被 futex_unlock_pi 唤醒时，由于被唤醒的进程还只是 pending owner，还挂在 PI chain 中，所以将 q.rt_waiter 保留，等回到 futex_wait_requeue_pi 真正成为 owner 以后，再将 rt_waiter 移出 PI chain。

这时，骇客的破解程序构造了一种反常的场景，让调用 futex_wait_requeue_pi 的进程被唤醒时看到 q.rt_waiter 被置 NULL，但 rt_waiter 却还挂在 PI chain 中（并非预想的那样没有被使用）。于是，futex_wait_requeue_pi 看到 q.rt_waiter 为 NULL，会认为 rt_waiter 并未使用，并不会去清理 PI chain。等 futex_wait_requeue_pi 返回之后，PI chain 里的 rt_waiter 就成了野指针（注意它原本是在栈上分配的）。然后，通过骇客对栈上数据的精心构造，可以让内核在处理 PI chain 的时候调用到栈上预埋下的破解代码……

骇客怎么在栈上预埋破解代码，那是另外一个 story（有兴趣可以参阅：http://tinyhack.com/2014/07/07/exploiting-the-futex-bug-and-uncovering-towelroot/）。我们现在关心的是，骇客如何构造出 q.rt_waiter 为 NULL，但 rt_waiter 却还挂在 PI chain 中的场景？

这样想，futex_cmp_requeue_pi 会认为 uaddr1 代表的是普通 futex，uaddr2 是 pi_futex，所以如果 waiter 被直接唤醒，那么它肯定不会使用 rt_mutex_waiter。

如果我们让 uaddr1 代表 pi_futex，想要的场景不就构造出来了么？futex_cmp_requeue_pi 认为 rt_mutex_waiter 没有使用，但它却已经被挂在了 uaddr1 对应的 PI chain 中。

好了，现在的问题是如何让 uaddr1 代表 pi_futex。直接调用 futex_wait_requeue_pi 是不行的，它不会把 uaddr1 当作 pi_futex，所以不会将 rt_mutex_waiter 挂上去。解决办法是先让 futex_wait_requeue_pi 的调用者被 requeue 一次（先调用一次 futex_cmp_requeue_pi 将其 requeue，需要构造另一个被直接唤醒的炮灰进程），从而使得 rt_mutex_waiter 被挂入 uaddr2 对应的 PI chain。

然后，此时再调用 futex_cmp_requeue_pi (uaddr2, uaddr3)，让 waiter 被直接唤醒，那不就大功告成了么！

先别高兴得太早，回顾一下之前的数据结构，futex_q 有一个成员叫做 requeue_pi_key，它会记录下调用 futex_wait_requeue_pi 时的 uaddr2。此时你想将它 requeue 到 uaddr3 上，那是糊弄不过去的。futex_cmp_requeue_pi 会检查 requeue 的目标一定等于 futex_q.requeue_pi_key。

但是，看似内核已经把路给堵死了，谁曾想居然还有这么一招：futex_cmp_requeue_pi (uaddr2, uaddr2)。由于 futex_cmp_requeue_pi 的 BUG，没有去检查两个 uaddr 是否不同，还真的就此被蒙混过关，成就了一个影响甚广的漏洞。